import java.util.*;

public class Solution {
    static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        TreeNode(int val){
            this.val = val;
        }
    }
    public static void inOrder(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> s = new Stack<>();
        while(true){
            while(root!=null){
                s.add(root);
                root = root.left;
            }
            if(s.empty())break;
            root = s.pop();
            System.out.println(root.val);
            root = root.right;
        }
    }
    public static void preOrder(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> s =new Stack<>();
        while(true){
            while(root!=null){
                System.out.println(root.val);
                s.add(root);
                root = root.left;
            }
            if(s.empty())break;
            root = s.pop();
            root = root.right;
        }
    }
    public static void postOrder(TreeNode root){
        if(root==null) return;
        TreeNode lastVisit = new TreeNode(-1);
        Stack<TreeNode> s = new Stack<>();
        while(root!=null){
            s.add(root);
            root = root.left;
        }
        while(!s.empty()){
            root = s.peek();
            if(root.right==null||root.right==lastVisit){
                root = s.pop();
                System.out.println(root.val);
                lastVisit = root;
            }else{
                root = root.right;
                while(root!=null){
                    s.add(root);
                    root = root.left;
                }
            }
        }
    }
    public static void levelOrder(TreeNode root){
        if(root==null) return;
        LinkedList<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            root = q.pollFirst();
            System.out.println(root.val);
            if(root.left!=null)
                q.add(root.left);
            if(root.right!=null)
                q.add(root.right);
        }

    }
    //s形层次遍历
    public static void levelOrderS(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.add(root);
        while(!s1.empty()|| s2.empty()){
            while(!s1.empty()){
                root = s1.pop();
                System.out.println(root.val);
                if(root.right!=null)
                s2.add(root.right);
                if(root.left!=null)
                s2.add(root.left);
            }
            while(!s2.empty()){
                root = s2.pop();
                System.out.println(root.val);
                if(root.left!=null)
                s1.add(root.left);
                if(root.right!=null)
                s1.add(root.right);
            }
        }

    }
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result  = new ArrayList<>();
        ArrayList<Integer> lineList ;
        Queue<TreeNode> queue = new ArrayDeque<>();
        TreeNode levelNode = new TreeNode(-1);
        TreeNode tempNode;
        if(pRoot==null)
            return result;
        else{
            queue.add(pRoot);
            queue.add(levelNode);
            lineList = new ArrayList<>();
            while(!queue.isEmpty()){
                tempNode = queue.poll();
                if(tempNode==levelNode){
                    result.add(lineList);
                    lineList=new ArrayList<>();
                    if(!queue.isEmpty())
                    queue.add(levelNode);
            }else{
                lineList.add(tempNode.val);
                if(tempNode.left!=null)
                    queue.add(tempNode.left);
                if(tempNode.right!=null)
                    queue.add(tempNode.right);
            }
            }
        }
        return result;
    }

    public static void main(String args[]){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node7;
        node3.right = node8;
//        inOrder(node1);
//        preOrder(node1);
//        postOrder(node1);
//        levelOrder(node1);
        levelOrderS(node1);
//        Print(node1);
        System.out.println();

    }

}

